package org.hhchat.leetcode.sort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created this one by HMH on 2017/5/27.
 */
public class code324 {

    public static class Solution {
        public void wiggleSort(int[] nums) {
            int n = nums.length;
            int mid = getKth(nums, 0, n - 1, (n + 1) / 2);
            List<Integer> leftarr = new ArrayList<>();
            for(int i=0;i<=mid;i++) {
                leftarr.add(nums[i]);
            }
            List<Integer> rightarr = new ArrayList<>();
            for(int i=mid+1;i<n;i++) {
                rightarr.add(nums[i]);
            }
            for(int li=leftarr.size()-1,ri=rightarr.size()-1,i = 0;ri>=0;li--,ri--,i+=2) {
                nums[i] = leftarr.get(li);
                nums[i + 1] = rightarr.get(ri);
            }
            if((n&1)==1){
                nums[n - 1] = leftarr.get(0);
            }
        }

        public int getKth(int[] nums,int l,int h,int k) {
            int[] range = partition(nums,l,h);
            if(k-1<range[0]){
                return getKth(nums,l,range[0]-1,k);
            }else if(k-1>range[1]){
                return getKth(nums, range[1] + 1, h, k);
            }else{
                return k-1;
            }
        }

        private int[] partition(int[] nums, int l, int h) {
            int pVal = nums[l];
            int i=l;
            while(i<=h){
                if(nums[i]==pVal){
                    i++;
                }
                else if(nums[i]<pVal){
                    swap(nums, i++, l++);
                }
                else{
                    swap(nums, i, h--);
                }
            }
            int[] res = new int[2];
            res[0]=l;
            res[1]=h;
            return res;
        }

        public static void swap(int[] nums, int op1, int op2) {
            int temp = nums[op2];
            nums[op2] = nums[op1];
            nums[op1] = temp;
        }
    }

    public static void main(String[] args){
        int[] test = new int[]{1,1,2,1,2,2,1};
        Solution solution = new Solution();
        solution.wiggleSort(test);
        System.out.println(Arrays.toString(test));
    }
}
